package runTime;

import TAProgram.OperatorType;
import TAProgram.TACode;
import TAProgram.ValueType;
import TAProgram.Variable;
import basicBlock.BasicBlock;

import java.util.*;

public class Optimizer {


    class Pair<A,B> {
        TACode taCode;
        A in;
        B out;
        public Pair(TACode taCode, A a, B b ) {
            this.taCode = taCode;
            this.in = a;
            this.out = b;
        }
    }

    public static void copy(LinkedHashMap<String,String> a,LinkedHashMap<String,String> b){
        Iterator<String> iterator = b.keySet().iterator();
        while(iterator.hasNext()){
            var key = iterator.next();
            var value = b.get(key);
            a.put(key,value);
        }
    }



    /**
     * 本地优化
     * 1.代数优化 ok
     * 2.常数折叠 ok
     * 3.删除公共子表达式
     * 4.拷贝传播、常数传播
     *
     * ~~~5.删除不可达的基本块~~~
     * 6.死代码删除
     *
     *
     */

    /**
     * 代数优化:
     *   1.x:=x+0 可以删除这一行代码
     *   2.x:=x*0 这一行代码可以简化成 x:=0
     *   3.x:=x*8 这一行代码可以优化成 x:=x<<3
     *
     *   tip: 删除代码调用TAcode.die(taCode)
     */
    public static void mathOpt(BasicBlock block){
        if(block == null) return;
        var head = block.getHead();
        if(head != null){
            if(head.getCodeSeq().equals("")){
                zeroCheck(head);
                sqrtCheck(head);
                constFold(head);
            }
        }
        var others = block.getOthers();
        if(others == null) return;
        for(var other : others){
            if(other.getCodeSeq().equals("")){
                zeroCheck(other);
                sqrtCheck(other);
                constFold(other);
            }
        }
    }

    private static int twoCheck(int num){
        if(num == 1) return -1;
        int start = 1;
        int cnt = 0;
        while(start < num){
            cnt++;
            start *= 2;
        }
        if(start == num) return cnt;
        return -1;
    }

    //乘除法优化成左移右移运算
    private static void sqrtCheck(TACode taCode){
        if(taCode.getOperator().getName() == null) return;
        int cnt = -1;
        if(taCode.getOperator().getName().equals("*")){
            if( taCode.getOperandA().getName() != null
                    && (taCode.getOperandB().getValueType() == ValueType.INTTYPE)
                    && ((cnt = twoCheck(taCode.getOperandB().getConstIntValue())) != -1)
            ){
                taCode.update(
                        new OperatorType("<<"),
                        taCode.getOperandA(),
                        new Variable(null,false,ValueType.INTTYPE,cnt),
                        taCode.getResult()
                );
            }else{
                if( taCode.getOperandB().getName() != null
                        && (taCode.getOperandA().getValueType() == ValueType.INTTYPE)
                        && ((cnt = twoCheck(taCode.getOperandA().getConstIntValue())) != -1)
                ){
                    taCode.update(
                            new OperatorType("<<"),
                            taCode.getOperandB(),
                            new Variable(null,false,ValueType.INTTYPE,cnt),
                            taCode.getResult()
                    );
                }
            }
        }else if(taCode.getOperator().getName().equals("/")){
            if( taCode.getOperandA().getName() != null
                    && (taCode.getOperandB().getValueType() == ValueType.INTTYPE)
                    && ((cnt = twoCheck(taCode.getOperandB().getConstIntValue())) != -1)
            ){
                taCode.update(
                        new OperatorType(">>"),
                        taCode.getOperandA(),
                        new Variable(null,false,ValueType.INTTYPE,cnt),
                        taCode.getResult()
                );
            }else{
                if( taCode.getOperandB().getName() != null
                        && (taCode.getOperandA().getValueType() == ValueType.INTTYPE)
                        && ((cnt = twoCheck(taCode.getOperandA().getConstIntValue())) != -1)
                ){
                    taCode.update(
                            new OperatorType(">>"),
                            taCode.getOperandB(),
                            new Variable(null,false,ValueType.INTTYPE,cnt),
                            taCode.getResult()
                    );
                }
            }
        }
    }

    //代数优化: 零项检查 删除+-0代码 简化*0代码
    public static void zeroCheck(TACode taCode){
        if(taCode.getResult().getName().equals("t2") && taCode.getOperandA().getName().equals("t2")){
            int ddd = 1;
        }
        if(taCode.getActive() == true){
            if( (taCode.getResult().getName().equals(taCode.getOperandA().getName())
                    && (taCode.getOperandB().getValueType().equals(ValueType.INTTYPE))
                    && (taCode.getOperandB().getConstIntValue() == 0))
                    || (taCode.getResult().getName().equals(taCode.getOperandB().getName())
                    && (taCode.getOperandA().getValueType().equals(ValueType.INTTYPE))
                    && (taCode.getOperandA().getConstIntValue() == 0))
            ){
                String operator = taCode.getOperator().getName();
                if(operator.equals("+")
                || operator.equals("-")){
                    TACode.die(taCode);
                }
                if(operator.equals("*")){
                    taCode.update(
                        new OperatorType((String) null),
                        new Variable(null,false,ValueType.INTTYPE,0),
                        new Variable((String) null),
                        taCode.getResult()
                    );
                }
            }
        }
    }


    /**
     * 常数折叠:
     *   1.三地址代码中如果两个操作数都是常数就可以编译时直接计算出来
     *   比如: “x:= 20 * 3 ”可以优化成“x:=60”
     *
     *   tip: 修改代码可以调用taCode.update(operator,operandA,operandB,result)
     */
    public static void constFold(TACode taCode){
        var operatorA = taCode.getOperandA();
        var operatorB = taCode.getOperandB();
        if(operatorA == null || operatorB == null) return;
        if(operatorA.getName().equals("") && operatorB.getName().equals("")
                && operatorA.getValueType() != null
                && operatorB.getValueType() != null
                && operatorA.getValueType().equals(ValueType.INTTYPE)
                && operatorB.getValueType().equals(ValueType.INTTYPE)){
            //暂时只检测int
            int a = operatorA.getConstIntValue();
            int b = operatorB.getConstIntValue();
            int result = 0;
            if ("+".equals(taCode.getOperator().getName())) {
                result = a + b;
            }else if("-".equals(taCode.getOperator().getName())){
                result = a - b;
            }else if("*".equals(taCode.getOperator().getName())){
                result = a * b;
            }//其它暂时省略
            taCode.update(
                new OperatorType((String) null),
                new Variable(null,false,ValueType.INTTYPE,result),
                new Variable((String) null),
                taCode.getResult()
            );
        }
    }

    /**
     * 基本块优化：计算可用表达式 进行本地优化 包括删除公共子表达式 和 拷贝传播
     * D：朝下
     * V：集合,表达式集合
     * F：转换函数,变量被重新赋值,就从集合中把原来的定义去掉替换成新的表达式来定义该变量
     * I：初始值,初始化集合为空
     */
    public static void expressionAnalyze(BasicBlock basicBlock) {
        //map:左边变量 右边表达式
        //1.map要能够按插入的顺序遍历
        //2.能删除key
        //3.能替换value
        ArrayList<LinkedHashMap<String,String>> expressionMaps = new ArrayList<>();
        var head = basicBlock.getHead();
        var others = basicBlock.getOthers();
        ArrayList<TACode> taCodes = new ArrayList<>();
        if(head != null) {
            if(head.getActive() == true) taCodes.add(head);
        }
        if(others != null){
            for(var other : others) {
                if(other.getActive() == true) taCodes.add(other);
            }
        }
        int length = taCodes.size();
        for(int i = 0; i< length;i++){
            LinkedHashMap<String, String> expressionMap = new LinkedHashMap<String,String>();
            LinkedHashMap<String, String> last = null;
            if( i > 0){
                last = expressionMaps.get(i-1);
                Optimizer.copy(expressionMap,last);
            }
            //当前的指令
            var taCode = taCodes.get(i);
            if(taCode.getResult().getName().equals("t3") && taCode.getOperandA() != null && taCode.getOperandA().getName().equals("a")){
                int ddd = 1;
            }
            var result = taCode.getResult();
            var expression = taCode.getExpression();
            expressionMap.put(taCode.getResult().getName(),taCode.getExpression());
            expressionMaps.add(i, expressionMap);
            if(last == null) continue;
            //1.删除公共子表达式
            for(int j = 0; j < i;j++){
                var curCode = taCodes.get(j);
                var pastMap = expressionMaps.get(j);
                var curVariableName = curCode.getResult().getName();
                if(pastMap.get(curVariableName).equals(expressionMap.get(taCode.getResult().getName()))){
                    //替换公共表达式为变量
                    taCode.update(
                            null,
                            curCode.getResult(),
                            null,
                            taCode.getResult()
                    );
                }
            }
            expressionMap.put(taCode.getResult().getName(),taCode.getExpression());
        }
        //需要一个变量变动 和 更新的点的时机的统计
        //在变动之间进行 拷贝传播 进行代码替换
        //所以需要一个TACodes数组
        //在更新和变更统计三元组 (a,1,4)   (b,2,5)

        //2.拷贝传播 b := a
        for(int i = 0; i < length;i ++ ){
            TACode taCodeB = taCodes.get(i);
            String variableB = taCodeB.getResult().getName();
            for(int j = 0;j < i; j ++ ){
                TACode taCodeA = taCodes.get(j);
                String variableA = taCodeA.getResult().getName();
                //b的右边 是一个赋值语句
                if(taCodeB.getExpression().equals(variableA)){
                    var start = expressionMaps.get(i);
                    LinkedHashMap<String,String> end;
                    int pos = i;
                    //找到b的值修改的位置
                    for(int index = i;index < length;index++){
                        var cur = expressionMaps.get(index);
                        if(cur.get(variableB).equals(start.get(variableB))){
                            end = cur;
                            pos = index;
                        }
                    }
                    //拷贝传播  index~pos之间的所有表达式b的地方 换成a
                    for(int index = i+1;index <= pos;index++){
                        var tacode = taCodes.get(index);
                        if(tacode.getOperandA().getName().equals(variableB)){
                            tacode.setOperandA(taCodeA.getResult());
                        }
                        if(tacode.getOperandB().getName().equals(variableB)){
                            tacode.setOperandB(taCodeA.getResult());
                        }
                        var map = expressionMaps.get(index);
                        map.put(tacode.getResult().getName(),tacode.getExpression());
                    }
                }
            }
        }
    }



}
